#include<vector>

//template<class T>
//class less {
//	bool operator()(const T& a, const T& b) {
//		return a < b;
//	}
//};

template<class T, class Container = vector<T>>
class priority_queue {
private:
	Container _con;
public:
	void up(int child) {
		//int parent = (child - 1) / 2;
		while (child && _con[child] > _con[(child - 1) / 2]) {
			swap(_con[child], _con[(child - 1) / 2]);
			child = (child - 1) / 2;
		}
	}

	void down(int parent) {
		int u = parent;
		if (parent * 2 + 1 < _con.size() && _con[parent * 2 + 1] > _con[u]) u = parent * 2 + 1;
		if (parent * 2 + 2 < _con.size() && _con[parent * 2 + 2] > _con[u]) u = parent * 2 + 2;
		if (parent != u) {
			swap(_con[parent], _con[u]);
			down(u);
		}
	}

	void push(const T& x) {
		_con.push_back(x);
		up(_con.size() - 1);
	}

	void pop() {
		swap(_con[0], _con[_con.size() - 1]);
		_con.pop_back();
		down(0);
	}

	const T& top() {
		return _con[0];
	}

	bool empty() {
		return _con.empty();
	}
	size_t size() {
		return _con.size();
	}

};

